package org.lisy.java.collection;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class HashMapOperate {
	/**
	 * Map 实现类
	 * 	1.Hashtable:底层是哈希表数据结构，不可以存入null值或者键，该集合是线程同步的
	 * 	2.HashMap:底层是哈希表数据结构，允许使用null的键值对，线程是不同步的。效率高
	 * 	3.TreeMap:底层是二叉树数据结构，线程不同步，允许使用null值和null键,按照自然顺序或比较器排序
	 *    -可以用于给map集合中的键进行排序,要求key实现compareable接口的compareTo方法，来判断往左子树还是右子树查
	 *  4.LinkedHashMap: 采用哈希值作为链表的key，构成一个链表
	 *  5.ConcurrentHashMap: 对桶数组进行了分段,在每一个分段上都用锁进行了保护
	 */
	
	/**
	 * HashMap特点
	 *  1. 数组+链表+红黑树(链表长度达到8，变为红黑树)
	 *  2. 使用(key == null) ? 0 : (h = key.hasahCode()) ^(h>>>16); 计算得到hash值，然后对当前容量进行取余操作(截取二进制的后n位)，确定数组下标
	 *  3. 如何保证key唯一：重写hashCode（）和equals（）方法
	 *  4. 线程不安全
	 */
	
	/**
	 * HashMap 类主要成员变量
	 *  transient int size: 记录了 Map 中 KV 对的个数
	 *  loadFactor: 装载因子，用来衡量 HashMap 满的程度。loadFactor 的默认值为 0.75f（static final float DEFAULT_LOAD_FACTOR = 0.75f;）
	 *  int threshold: 临界值，当实际 KV 个数超过 threshold 时，HashMap 会将容量 扩容，threshold＝容量*装载因子
	 *  capacity: 容量，如果不指定，默认容量是 16(static final int DEFAULT_I NITIAL_CAPACITY = 1 << 4;)
	 */
	
	/**
	 * HashMap 中 hash 方法的原理
	 * 
	 * 1.哈希
	 *   Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入， 通过散列算法，变换成固定长度的输出，该输出就是散列值这种
	 * 转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。
	 * 简单的说就是一种将任意长度的消息压缩到某一固定长 度的消息摘要的函数
	 *   所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值
	 * 如果相同，输入值不一定相同
	 *   两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞
	 * 常见的 Hash 函数：
	 *   直接定址法：直接以关键字 k 或者 k 加上某个常数（k+c）作为哈希地址
	 *   数字分析法：提取关键字中取值比较均匀的数字作为哈希地址
	 *   除留余数法：用关键字 k 除以某个不大于哈希表长度 m 的数 p，将所得余数作为哈希表地址
	 *   分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址
	 *   平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址
	 *   伪随机数法：采用一个伪随机数当作哈希函数
	 * 衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案：
	 *   开放定址法: 一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
	 *   链地址法: 将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部
	 *   再哈希法: 当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止
	 *   建立公共溢出区: 将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中
	 * 
	 * 2.HashMap 的数据结构
	 *   常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组
	 *   我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征
	 * 计算元素数组下标的方法就是哈希算法，即 hash()函数（当然，还包括 indexOf()函数）
	 * 
	 * 3.hash 方法
	 *   hash ：该方法主要是将 Object 转换成一个整型
	 *   indexFor ：该方法主要是将 hash 生成的整型转换成链表数组中的下标。 
	 *   
	 *   HashMap In Java 7
   	 *   HashMap 的数据是存储在链表数组里面的。在对 HashMap 进行插入/删除等操作时，都需要根据 K-V 对的键值定位到他应该保存在数组的哪个下标中。
	 * 而这个通过键值求取下标的操作就叫做哈希。HashMap 的数组是有长度的，Java 中规定这个长度只能是 2 的倍数，初始值为 16。简单的做法是先求取出
	 * 键值的 hashcode，然后在将 hashcode 得到的 int 值对数组长度进行取模。为了考虑性能，Java 总采用按位与操作实现取模操作
	 *   indexFor 方法采用的是位运算，源码 return h & (length-1); 只要保证 length 的长度是 2^n 的话，就可以实现取模运算了,相当于 h % length
	 *   hash 方法
	 *     h ^= k.hashCode(); 
	 *     h ^= (h >>> 20) ^ (h >>> 12); 
	 *     return h ^ (h >>> 7) ^ (h >>> 4);
	 *   这里java解决哈希冲突的方式，对 key 的 hashCode 进行扰动计算，防止不同 hashCode 的高位不同但低位相同导致的 hash 冲突。简单点说，就是为了把高位
	 * 的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。除了性能之外，还有一个好处
	 * 就是可以很好的解决负数的问题(hashcode 的结果是 int 类型即[ -2147483648, 2147483647])
	 *   * HashMap 默认的初始化大小为 16，之后每次扩充为原来的 2 倍
	 *   * 在取模计算时，如果模数是 2 的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法；又引入了哈希分布不均匀的问题，所以 HashMap 为
	 * 解决这问题，又对 hash 算法做了一些改进，进行了扰动计算
	 *   
	 *   HashTable In Java 7
	 *   HashTable没有 indexOf 方法，hash 方法采用的是直接取模，源码 int index = (hash & 0x7FFFFFFF) % tab.length; 位与操作为了保证得到正数。
	 * 由于 HashTable 会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀，hash 结果越分散效果越好
	 *   * HashTable 默认的初始大小为 11，之后每次扩充为原来的 2n+1
	 *   
	 *   ConcurrentHashMap In Java 7
	 *   ConcurrentHashMap 的 hash 实现其实和 HashMap 如出一辙。都是通过位运算代替取模，然后再对 hashcode 进行扰动，使用了一种变种的 Wang/Jenkins 哈希
	 * 算法，其主要目的也是为了把高位和低位组合在一起，避免发生冲突，不能证明和 HashMap 的扰动算法哪个更优
	 * 
	 *   HashMap In Java 8
	 *   为了解决在频繁冲突时 hashmap 性能降低的问题，Java 8 中使用平衡树来替代链表存储冲突的元素，可以将最坏情况下的性能从 O(n)提高到 O(logn)
	 *   如果恶意程序知道我们用的是 Hash 算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些 key 导致 HashMap 忙于进行线性
	 * 查找，最终陷入瘫痪，即形成了拒绝服务攻击（DoS）
	 *   hash 方法，Java 8 中这一步做了优化，只做一次 16 位右位移异或混合，而不是四次，原理是不变的
	 *     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
	 *   
	 *   HashTable In Java 8
	 *   没有 hash 方法，哈希的操作还在， 比如在 put 方法中实现和 Java 7 中的实现几乎无差别: 
	 *    int hash = key.hashCode(); 
	 *    int index = (hash & 0x7FFFFFFF) % tab.length;
	 *   
	 *   ConcurrentHashMap In Java 8
	 *   求 hash 的方法从 hash 改为了 spread。实现方式如下: 
	 *     static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; }
	 *   Java 8 的 ConcurrentHashMap 作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，所以作者并未在哈希值的计算上做过多设计，
	 * 只是将 Key 的 hashCode 值与其高 16 位作异或并保证最高位为 0（从而保证最终结果为正整数）
	 */
	
	/**
	 * HashMap 的容量
	 *   HashMap 将数组和链表组合在一起，可以将其理解为链表的数组
	 *   
	 *   默认容量
	 *   创建 HashMap 时不指定容量，默认容量为 16 ，默认容量的定义为：static final int DEFAULT_INITIAL_ CAPACITY = 1 << 4; // aka 16，
	 * 作者故意把 16 写成 1<<4，就是提醒开发者，这个地方要是 2 的幂，通过 HashMap(int initialCapacity)设置初始容量的时，HashMap 并不一定会直接采用
	 * 传入的数值，而是经过计算，得到一个新值，目的是提高 hash 的效率。(1->1、3->4、7->8、9->16)，得到第一个比他大的 2 的幂并返回源码:
	 *     int n = cap - 1; 
	 *     n |= n >>> 1; 
	 *     n |= n >>> 2; 
	 *     n |= n >>> 4; 
	 *     n |= n >>> 8; 
	 *     n |= n >>> 16; 
	 *     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
	 *   
	 *   扩容
	 *   当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容，扩容到之前容量的 2 倍: 
	 *     if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {newThr = oldThr << 1; // double threshold }
	 *   
	 *   设置初始化容量
	 *   如果没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多次扩容，每次扩容都需要重建 hash 表，是非常影响性能的，设置值参考方法:
	 *     return (int) ((float) expectedSize / 0.75F + 1.0F);
	 *   这个算法在 guava 中有实现，开发的时候，可以直接通过 Maps 类创建一个HashMap (内存换性能)：
	 *     Map<String, String> map = Maps.newHashMapWithExpectedSize(7);
	 */
	
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();

        // 添加元素
        map.put("001", "zhangsan");
        map.put("002", "lisi");
        map.put("003", "wangwu");

        System.out.println("collection: " + map);

        // 判断是否存在002的key
        System.out.println(map.containsKey("002"));
        
        // 刪除
        map.remove("002");
        System.out.println("delete: " + map);

        // 获取
        System.out.println("get: " + map.get("001"));

        // 可以通过get方法的返回值来判断一个键是否存在
        map.put(null, "haha");
        System.out.println("null: " + map);

        // 获取map集合中所有的值
        Collection<String> values = map.values();
        System.out.println("map value: " + values);
        
        // keySet遍历
        Set<String> keySet = map.keySet();

        Iterator<String> iterator = keySet.iterator();

        while (iterator.hasNext()) {
            String string = iterator.next();
            // 有了键可以通过map集合的get方法获取其对应的值
            String value = map.get(string);
            System.out.println("key:" + string + " values:" + value);
        }
        
        // entrySet遍历, 将map集合中的映射关系取出，存入到Set集合中
        Set<Entry<String, String>> entrySet = map.entrySet();

        Iterator<Entry<String, String>> iterator1 = entrySet.iterator();

        while (iterator1.hasNext()) {
            Map.Entry<String, String> entry = iterator1.next();
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }
}
